package com.lw.leetcode.arr.a;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 942. 增减字符串匹配
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/9 9:11
 */
public class DiStringMatch {

    public static void main(String[] args) {
        DiStringMatch test = new DiStringMatch();

        // [0,4,1,3,2]
//        String str = "IDID";

        // [3,2,0,1]
        String str = "DDI";


        int[] ints = test.diStringMatch(str);
        System.out.println(Arrays.toString(ints));

    }

    public int[] diStringMatch(String S) {
        int length = S.length();
        int[] arr = new int[length + 1];
        char[] chars = S.toCharArray();
        int st = 0;
        int end = length;
        int index = 0;
        while (st < end) {
            if (chars[index] == 'I') {
                arr[index++] = st++;
            } else {
                arr[index++] = end--;
            }
        }
        arr[index] = st;
        return arr;
    }

    public int[] diStringMatch2(String S) {
        int length = S.length();
        int[] arr = new int[length + 1];
        char[] chars = S.toCharArray();
        int max = 1;
        int min = -1;
        arr[0] = 0;
        for (int i = 0; i < length; i++) {
            if (chars[i] == 'I') {
                arr[i + 1] = max++;
            } else {
                arr[i + 1] = min--;
            }
        }
        for (int i = 0; i <= length; i++) {
            arr[i] = arr[i] - min - 1;
        }
        return arr;
    }

}
